#include <stdio.h>
#include <stdlib.h>

typedef char DataType;

typedef struct node {
    DataType data;
    struct node *next;
    struct node *front;
} LinkQueue;

LinkQueue *init() {

    LinkQueue *top = (LinkQueue *) malloc(sizeof(LinkQueue));
    top->data = '0';
    top->next = NULL;
    top->front = top;

    return top;
}

LinkQueue *push(LinkQueue *queue, DataType data) {

    LinkQueue *node = (LinkQueue *) malloc(sizeof(LinkQueue));
    node->data = data;
    node->next = NULL;
    node->front = queue->front;

    queue->next = node;

    return node;
}

int isEmpty(LinkQueue *queue) {
    return queue->front->next == NULL;
}

LinkQueue *pop(LinkQueue *rear) {

    if (isEmpty(rear)) {
        printf("queue is empty!\n");
        return rear;
    }

    LinkQueue *front = rear->front;
    LinkQueue *item = front->next;

    front->next = item->next;
    printf("pop value %c\n", item->data);

    // 如果没有元素了，就指向结点
    if (item->next == NULL) {
        rear = front;
    }

    free(item);

    return rear;
}


void toString(LinkQueue *queue) {

    LinkQueue *p = queue->next;

    printf("[");
    while (p != NULL) {
        printf("%c,", p->data);
        p = p->next;
    }
    printf("]\n");

}


int main() {
    printf("LinkQueue!\n");

    LinkQueue *rear = init();

    rear = push(rear, 'a');
    rear = push(rear, 'b');
    rear = push(rear, 'c');

    toString(rear->front);

    rear = pop(rear);
    rear = pop(rear);
    rear = pop(rear);
    rear = pop(rear);
    rear = pop(rear);
    toString(rear->front);

    rear = push(rear, '1');
    rear = push(rear, '2');
    rear = push(rear, '3');
    rear = push(rear, '4');
    toString(rear->front);

    rear = pop(rear);
    rear = pop(rear);
    toString(rear->front);

    rear = push(rear, '5');
    rear = push(rear, '6');
    toString(rear->front);

    return 0;
}
